package com.myown.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 最大子数组算法
 *
 * @author lincky
 * @version v1.0.0
 * @time 2016/12/19 19:00
 */

public class Subarray {

    public static class Result {
        int max = 0;
        int low = 0;
        int high = 0;

        Result(int max, int low, int high) {
            this.max = max;
            this.low = low;
            this.high = high;
        }

        Result() {

        }
    }

    /**
     * 分治算法求解最大子数组 <p>
     *
     * 时间复杂度：O（n*logn）<p>
     *
     * @param list 数组
     * @param low  数组起始索引
     * @param high 数组终止索引
     * @return Result 结果封装对象
     */
    public static Result findMaxSubarrayDividing(List<Integer> list,
                                                 int low,
                                                 int high) {
        if (low == high) {
            return new Result(list.get(low), low, high);
        } else {
            int off = (low + high) / 2;
            Result leftSubarrayResult = findMaxSubarrayDividing(list, low, off);
            Result rightSubarrayResult = findMaxSubarrayDividing(list, off + 1, high);
            Result crossingSubarrayResult = findMaxCrossingSubarray(list, low, high, off);
            if (leftSubarrayResult.max >= rightSubarrayResult.max &&
                    leftSubarrayResult.max >= crossingSubarrayResult.max) {
                return leftSubarrayResult;
            } else if (rightSubarrayResult.max >= leftSubarrayResult.max &&
                    rightSubarrayResult.max >= crossingSubarrayResult.max) {
                return rightSubarrayResult;
            } else {
                return crossingSubarrayResult;
            }
        }
    }

    private static Result findMaxCrossingSubarray(List<Integer> list,
                                                  int low,
                                                  int high,
                                                  int off) {
        int sum_left = Integer.MIN_VALUE;
        int sum = 0;
        int max_left = 0;
        for (int i = off; i >= low; i--) {
            sum += list.get(i);
            if (sum > sum_left) {
                sum_left = sum;
                max_left = i;
            }
        }
        sum = 0;
        int sum_right = Integer.MIN_VALUE;
        int max_right = 0;
        for (int i = off + 1; i <= high; i++) {
            sum += list.get(i);
            if (sum > sum_right) {
                sum_right = sum;
                max_right = i;
            }
        }
        return new Result(sum_left + sum_right, max_left, max_right);
    }

    /**
     * 线性时间内求解最大子数组 <p>
     *
     * 时间复杂度：O（n）<p>
     *
     * @param list 数组
     * @param low  数组起始索引
     * @param high 数组终止索引
     * @return Result 结果封装对象
     */
    public static Result findMaxSubarray(List<Integer> list,
                                         int low,
                                         int high) {
        int MaxSum = 0;
        int CurSum = 0;
        int max_low = low;
        int max_high = high;
        int temp = low;
        for (int i = low; i <= high; i++) {
            CurSum += list.get(i);
            if (CurSum > MaxSum) {
                MaxSum = CurSum;
                max_high = i;
                max_low = temp;
            }

            if (CurSum < 0) {
                CurSum = 0;
                temp = i + 1;
            }
        }
        return new Result(MaxSum, max_low, max_high);

    }

    public static List<Integer> getRangeList(List<Integer> list, Integer low, Integer high) {
        List<Integer> rangeList = new ArrayList<>();
        for (int i = low; i <= high; i++) {
            rangeList.add(list.get(i));
        }
        return rangeList;
    }
}
